//
// Created by ASUS on 2024/12/11/星期三.
//
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;  // 根据实际数据范围调整

// 线段树节点结构体
struct Node {
	int lson, rson;
	int cnt;  // 该节点所代表区间内的元素个数
} tree[MAXN * 20];

int tot = 0;
vector<int> a;  // 原数组离散化后的结果
int root[MAXN];  // root[i]表示第i个版本线段树的根节点编号

// 离散化函数，将原数组离散化
vector<int> discrete(vector<int>& arr) {
	vector<int> b = arr;
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for (int i = 0; i < arr.size(); ++i) {
		arr[i] = lower_bound(b.begin(), b.end(), arr[i]) - b.begin();
	}
	return b;
}

// 构建可持久化线段树，now为当前节点编号，l和r为当前区间左右端点，val为要插入的值
int build(int now, int l, int r, int val) {
	int cur = ++tot;
	tree[cur] = tree[now];
	if (l == r) {
		tree[cur].cnt++;
		return cur;
	}
	int mid = (l + r) >> 1;
	if (val <= mid) {
		tree[cur].lson = build(tree[now].lson, l, mid, val);
	} else {
		tree[cur].rson = build(tree[now].rson, mid + 1, r, val);
	}
	tree[cur].cnt = tree[tree[cur].lson].cnt + tree[tree[cur].rson].cnt;
	return cur;
}

// 查询区间第k小值，l和r为当前查询区间左右端点，ql和qr为目标区间左右端点，k为要查询的第k小
int query(int l, int r, int ql, int qr, int k) {
	if (l == r) return l;
	int sum = tree[tree[qr].lson].cnt - tree[tree[ql].lson].cnt;
	int mid = (l + r) >> 1;
	if (k <= sum) {
		return query(l, mid, tree[ql].lson, tree[qr].lson, k);
	} else {
		return query(mid + 1, r, tree[ql].rson, tree[qr].rson, k - sum);
	}
}

int main() {
	vector<int> arr = {5, 3, 7, 1, 9, 2};  // 示例原数组
	a = discrete(arr);
	root[0] = build(0, 0, a.size() - 1, a[0]);
	for (int i = 1; i < arr.size(); ++i) {
		root[i] = build(root[i - 1], 0, a.size() - 1, a[i]);
	}
	// 查询区间[1, 4]的第3小值（这里索引从0开始，所以实际对应原数组第2到第5个元素的区间）
	int result = query(0, a.size() - 1, root[0], root[4], 3);
	cout << "区间[1, 4]的第3小值对应的离散化后的值为: " << result << endl;
	// 如果需要知道原数组中对应的真实值，还需要根据离散化后的映射关系查找
	cout << "区间[1, 4]的第3小值对应的原数组中的值为: " << a[result] << endl;

	return 0;
}